RAID (Redundant Array of Independent/Inexpensive Disks) is an organization of data on a plurality of disks which results in enhanced data availability and performance. As is well known, there are several levels of RAID organization with different characteristics that affect performance and availability. One performance enhancing feature of RAID is "striping" which spreads user data across the disks in the array. RAID enhances availability of data through data redundancy.
RAID level 4 (RAID-4) and RAID level 5 (RAID-5) are organizations of data on an array of n+1 disks that provide enhanced performance through the use of striping and enhanced data availability through the association of a parity block with every n data blocks. A block is the smallest unit of data that can be read or written to a disk. Each disk in the RAID array is referred to as a member of the array. Furthermore, while disks are referred to throughout, any equivalent storage media could be used as would be apparent to one of ordinary skill in the field. The data and parity information is distributed over the n+1 disks. Since RAID-4 and RAID-5 are organizations of data in which the data and parity information is distributed over the n+1 disks in the RAID array, if a single disk fails, all of the unavailable data can be reconstructed. RAID-4 is a level of organization of data for a RAID array where data blocks are organized into chunks which are interleaved among the disks and protected by parity and all of the parity is written on a single disk. RAID-5 is a level of organization of data for a RAID array where data blocks are organized into chunks which are interleaved among the disks and protected by parity and the parity information is distributed over all of the disks in the array. A chunk is a group of consecutively numbered blocks that are placed consecutively on a single disk before placing blocks on a different disk. Thus, a chunk is the unit of data interleaving for a RAID array. A strip is the collection of a parity chunk and all of the data chunks that contribute to it.
The contents of each bit of the parity block is the Exclusive-OR of the corresponding bit in each of the n corresponding data blocks. In the event of the failure of a single disk in the array, the data from a given data block on the failed disk is recovered by computing the Exclusive-OR of the contents of the corresponding parity blocks and the n-1 data blocks on the surviving disks that contributed to that parity block. A block or set of blocks is repaired by writing the regenerated data. The regeneration and repair of data for a data block or set of data blocks on a disk in a RAID array is referred to as reconstruction.
As is well known, RAID-4 and RAID-5 organization is a collection of strips, each of which contains a set of blocks per disk, referred to as a chunk. In the RAID-4 organization, all parity chunks are stored on the same disk of the array. In the RAID-5 organization, parity chunks are located on different disks of the array in successive strips.
RAID storage systems can be implemented in hardware or software. In the hardware implementation the RAID algorithms are built into a controller that connects to the computer I/O bus. In the software implementation the RAID algorithms are incorporated into software that runs on the main processor in conjunction with the operating system. In addition, the software implementation can be affected through software running on a well known RAID controller. Both the hardware and software implementations of RAID are well known to those of ordinary skill in the field.
When a disk in the RAID array fails, it can be replaced with a new disk and the contents of the failed disk reconstructed using the standard RAID algorithms from the contents of the other disks. In this manner, the RAID array with the replacement disk is restored to its fully redundant state without the loss of application data.
To restore a failed disk of a RAID-4 or RAID-5 array the appropriate contents of the replacement disk must be computed and written to the replacement disk. The reconstruction is easy to implement if concurrent application access to the array is inhibited. If concurrent application access to the array is permitted during reconstruction, the read and write operations from the user must be performed in a manner that recognizes the state and operation of the restoration process. In known storage systems using RAID organization on-line reconstruction of a replacement disk is accomplished by using a "fence" that separates the portion of the disk that has been restored from the part that has not been restored. The read and write operations being performed differently depending upon which "side" of the "fence" they address. As restoration proceeds throughout the array the "fence" moves. The use of "fences" to effect on-line restoration requires complex programming and/or circuitry and accordingly increases the cost of the storage system. Thus, it is desirable to have an on-line restoration of a replacement disk to a RAID array while allowing high performance concurrent application access to the array.